package jasymca;

import geogebra.main.Application;

/**
 * A little bit of Lisp Basic Lisp/Scheme functions, mostly adapted from Norvigs
 * JScheme (www.norvig.org) Amazingly, it is possible to code Scheme programs in
 * Java with few changes The Java code does not conform to any standard.
 */
public class Lisp {
  static final boolean debug = false;
  // return list of bindings, or "MATCH", or null (no match)
  // pat = (x + 4 y); input = (2 + 3 + 4 2) --> ((x . 2.0 + 3.0) (y . 2.0))
  static final String MATCH = "#!MATCH";

  static Object inpr_rules = null;

  // A list of rules, ordered by precedence.
  static String[][] inpr_rules_in = {{"x , y", ", x y"}, {"x : y", ": x y"},
      {"x & y", "& x y"}, {"x = y", "- x y"}, {"x + y", "+ x y"},
      {"x - y", "- x y"}, {"- x", "- x"}, {"+ x", "+ x"},
      {"d y / d x", "d y x"}, {"Int y d x", "int y x"}, {"x * y", "* x y"},
      {"x / y", "/ x y"}, {"x !", "! x"}, {"x ^ y", "^ x y"}};

  // is this a list of Algebraics
  public static boolean algebraicq(Object x) {
    try {
      // Class a = Class.forName("jasymca.Algebraic");
      Class<Algebraic> a = jasymca.Algebraic.class;
      return kindof(x, a);
    } catch (Exception e) {
      throw new RuntimeException("Installation Error.");
    }
  }

  static Object append(Object x, Object y) {
    if (x instanceof Pair)
      return cons(car(x), append(cdr(x), y));
    else
      return y;
  }

  // convert arg1 op arg2 op arg3 .... to prefix form
  public static Object args_prefix(String op, Zahl identity, Object args) {
    args = remove(identity, args);
    if (args == null)
      return identity;
    if (op.equals("*") && member(Zahl.ZERO, args))
      return Zahl.ZERO;
    if (length(args) == 1)
      return car(args);
    Object result = list(op);
    for (Object arg = car(args); arg != null; args = cdr(args), arg = car(args))
      if (op.equals(car(arg)))
        result = append(result, cdr(arg));
      else
        result = append(result, list(arg));
    return result;
  }

  public static Object car(Object a) {
    if (a instanceof Pair)
      return ((Pair) a).car;
    return null;
  }

  public static Object cdr(Object a) {
    if (a instanceof Pair)
      return ((Pair) a).cdr;
    return null;
  }

  // Example: exp = (sin x + z)
  // match_pairs = ((x . 3) (z . 4))
  // result = (sin 3 + 4)
  public static Object change(Object exp, Object match_pairs) {
    if (!(match_pairs instanceof Pair))
      return exp;
    Object r = null;
    while (exp instanceof Pair) {
      // Experimental: Allows substitutions of complex expressions,e.g
      // x^2+2, x-1, y+x-1 ---> y+x^2-1
      Object sp = car(exp);
      Object mp = match_pairs;
      while (mp instanceof Pair) {
        Pair m = (Pair) car(mp);
        if (sp.equals(m.car)) {
          r = cons(m.cdr, r);
          break;
        } else
          mp = cdr(mp);
      }
      if (listq(sp) && !(mp instanceof Pair)) {
        r = cons(change(sp, match_pairs), r);
        exp = cdr(exp);
        continue;
      }

      if (!(mp instanceof Pair)) // No match found
        r = cons(sp, r);
      exp = cdr(exp);
      /*
       * Object sp = car(exp); if(listq(sp)){ r =
       * cons(change(sp,match_pairs),r); exp = cdr(exp); continue; } Object mp =
       * match_pairs; while(mp instanceof Pair){ Pair m = (Pair)car(mp);
       * if(sp.equals(m.car)){ r = cons(m.cdr, r); break; }else mp = cdr(mp); }
       * if(!(mp instanceof Pair)) // No match found r = cons(sp, r); exp =
       * cdr(exp);
       */
    }
    return reverse(r);
  }

  public static Object compile_rule(String s) throws ParseException {
    return in_pr(expandMult(read(s)));
  }

  public static Object compile_rules(String[][] rules) {
    Object r = null;
    for (String[] rule : rules)
      try {
        Object pat = compile_rule(rule[0]);
        Object exp = compile_rule(rule[1]);
        r = cons(cons(pat, exp), r);
      } catch (Exception e) {
      }
    return reverse(r);
  }

  public static Pair cons(Object a, Object b) {
    return new Pair(a, b);
  }

  public static boolean equal(Object a, Object b) {
    return a == null ? b == null : a.equals(b);
  }

  public static Object exp_lhs(Object expr) {
    return car(cdr(expr));
  }

  // convert canonical base^exponent to prefix form.
  public static Object exp_pr(Object base, int exponent) {
    switch (exponent) {
      case 0 :
        return Zahl.ONE;
      case 1 :
        return base;
      default :
        return cons("^", cons(base, list(new Unexakt(exponent))));
    }
  }

  public static Object exp_rhs(Object expr) {
    return list2atom(cdr(cdr(expr)));
  }

  // Input and Output are Prefix format
  public static Object expand(Object expr, Object rules) {
    switch (length(expr)) {
      case 0 :
        return expr;
      case 1 :
        return expand(car(expr), rules);
      default :
        Object r = translator(rules, expr);
        if (r != null)
          // Applied rule, try more
          return expand(r, rules);
        // No rule applied:
        // Break up list and apply rules to each car
        while (expr instanceof Pair) {
          r = cons(expand(car(expr), rules), r);
          expr = cdr(expr);
        }
        return reverse(r);
    }
  }

  // Expand "**": a**b ---> a ^ b
  public static Object expandExp(Object x) {
    if (!(x instanceof Pair))
      return x;
    Object r = null;
    while (x instanceof Pair) {
      Object next = car(x);
      // if(next.equals("*") && car(cdr(x)).equals("*")){
      if ("*".equals(next) && "*".equals(car(cdr(x)))) {
        r = cons("^", r);
        x = cdr(x);
      } else
        r = cons(expandExp(next), r);
      x = cdr(x);
    }
    return reverse(r);
  }

  // Expand ":=": a:=b ---> a & b
  // We use single character operators
  public static Object expandFundef(Object x) {
    if (!(x instanceof Pair))
      return x;
    Object r = null;
    while (x instanceof Pair) {
      Object next = car(x);
      if (":".equals(next) && "=".equals(car(cdr(x)))) {
        r = cons("&", r);
        x = cdr(x);
      } else
        r = cons(expandExp(next), r);
      x = cdr(x);
    }
    return reverse(r);
  }

  // Intersperse "*": a b ---> a * b
  // Not used any more
  public static Object expandMult(Object x) {
    if (!(x instanceof Pair))
      return x;
    Object lhs = car(x), rhs = car(cdr(x));
    if (lhs != null && rhs != null && noop(lhs) && noinfixop(rhs))
      return cons(expandMult(lhs), cons("*", expandMult(cdr(x))));
    else
      return cons(expandMult(lhs), expandMult(cdr(x)));
  }

  public static Object expConstant(String s) {
    // Numeric constants
    if (s.equalsIgnoreCase("i"))
      return Zahl.IONE;
    else
      return s;
  }

  public static Object in_pr(Object expr) {
    if (inpr_rules == null)
      inpr_rules = makeRules(inpr_rules_in);
    switch (length(expr)) {
      case 0 :
        return expr;
      case 1 :
        return in_pr(car(expr));
      default :
        Object r = translator(inpr_rules, expr);
        if (r != null) {
          int len = length(r);
          if (len == 2)
            return cons(car(r), list(in_pr(exp_lhs(r))));
          else
            return cons(car(r),
                list(in_pr(exp_lhs(r)), list(in_pr(exp_rhs(r)))));
        }
        if (car(expr) instanceof String)
          return list(car(expr), list(in_pr(cdr(expr))));

        // TODO: remove
        try {
          throw new Exception("Illegal expression: " + expr);

        } catch (Exception e) {
          e.printStackTrace();
        }

        Application.debug("Illegal expression: " + expr);
        return null;
    }
  }

  // is this a list of Objects of type c
  public static boolean kindof(Object x, Class<Algebraic> c) {
    if (c.isInstance(x))
      return true;
    if (!(x instanceof Pair))
      return false;
    while (x instanceof Pair) {
      if (!c.isInstance(car(x)))
        return false;
      x = cdr(x);
    }
    return true;
  }

  public static int length(Object x) {
    int len = 0;
    while (x instanceof Pair) {
      len++;
      x = cdr(x);
    }
    return len;
  }

  public static Pair list(Object a) {
    return new Pair(a, null);
  }

  public static Object list(Object a, Object b) {
    if (listq(b))
      return cons(a, b);
    return cons(a, list(b));
  }

  static Object list2atom(Object x) {
    return length(x) == 1 ? car(x) : x;
  }

  static boolean listq(Object x) {
    if (x == null)
      return true; // empty list
    if (!(x instanceof Pair))
      return false;
    return listq(cdr(x));
  }

  // This simple parser is adapted from Norvig's
  // book. It saves more than 50% space compared
  // to a solution based on javacc and jjtree
  // and is sufficient for our purpose

  static Object makeRules(String[][] rules_in) {
    Object r = null;
    for (String[] element : rules_in)
      try {
        Object pat = read(element[0]);
        Object exp = read(element[1]);
        r = cons(cons(pat, exp), r);
      } catch (Exception e) {
      }
    return reverse(r);
  }

  // Also reverse inner lists
  public static Object mapreverse(Object x) {
    if (!(x instanceof Pair))
      return x;
    Object r = null;
    while (x instanceof Pair) {
      r = cons(mapreverse(car(x)), r);
      x = cdr(x);
    }
    return r;
  }

  // Different Match conditions
  // x,y,z match anything
  // a,b,c match anything except some operators; not used
  static boolean matches(Object var, Object x) {
    switch (((String) var).charAt(0)) {
      case 'x' :
      case 'y' :
      case 'z' :
        return true;
      case 'a' :
      case 'b' :
      case 'c' :
        return noop(x);
    }
    return false;
  }

  static boolean member(Object x, Object args) {
    while (args instanceof Pair) {
      if (car(args).equals(x))
        return true;
      args = cdr(args);
    }
    return false;
  }

  // Break up String s into Objects
  // Objects are Numbers, Strings separated by meaning, lists of Objects (x1 x2
  // x3)
  // and vektors [ x1 x2 x3 ]
  public static Object nextObject(StringBuffer s) throws ParseException {
    int i = 0;
    while (i < s.length() && whitespace(s.charAt(i)))
      i++;
    if (i == s.length())
      return null;
    char c = s.charAt(i);
    switch (c) {
      case '"' :// Read string until next "
        s.delete(0, i + 1);
        String st = s.toString();
        i = st.indexOf('"');
        if (i < 0)
          throw new ParseException("Unclosed Quote.");
        st = st.substring(0, i);
        s.delete(0, i + 1);
        return st;
      case '(' :
        // Read list, recurse until ')'
        Object result = null,
        next;
        s.delete(0, i + 1);
        while (!")".equals(next = nextObject(s))) {
          if (next == null && s.length() == 0)
            throw new ParseException("Unclosed Parentheses.");
          result = cons(next, result);
        }
        return reverse(result);
      case '[' :
        // Read vektor, recurse until ']'
        result = null;// Use # to mark vectors
        s.delete(0, i + 1);
        while (!"]".equals(next = nextObject(s))) {
          if (next == null && s.length() == 0)
            throw new ParseException("Unclosed Parentheses.");
          result = cons(next, result);
        }
        return cons("#", list(reverse(result))); // Mark vektors with #
      case ')' :
      case ']' :
      case '+' :
      case '-' :
      case ',' :
      case '=' :
      case '*' :
      case '/' :
      case '^' :
      case '!' :
      case ':' :
        s.delete(0, i + 1);
        return String.valueOf(c);
      default : // Try to read number
        for (int k = s.length(); k > i; k--)
          try {
            double x = Double.parseDouble(s.toString().substring(i, k));
            s.delete(0, k);

            // BEGIN Markus Hohenwarter:
            // keep Integers als Exakt numbers
            // long xround = Math.round(x);
            // if (xround == x)
            // return new Exakt( BigInteger.valueOf(xround));
            // END Markus Hohenwarter

            return new Unexakt(x);
          } catch (Exception e) {
          }
        // Ok, no number and no operator: must be variable
        // Read until next symbol
        int k = i + 1;
        while (k < s.length() && !oneof(s.charAt(k), "()[]\n\t\r +-*/^!,:="))
          k++;
        String t = s.toString().substring(i, k);
        s.delete(0, k);
        return expConstant(t);
    }
  }

  public static boolean noinfixop(Object x) {
    return !(x instanceof String) || ((String) x).length() != 1
        || !oneof(((String) x).charAt(0), "^:+-*/!,=");
  }

  public static boolean noop(Object x) {
    if (!(x instanceof String))
      return false;
    Object a = Lambda.env.getValue((String) x);
    return !(a instanceof Lambda);
  }

  // is this a list of Numbers
  public static boolean numbers(Object x) {
    if (x instanceof Zahl || x instanceof Vektor && ((Vektor) x).number())
      return true;
    if (!(x instanceof Pair))
      return false;
    while (x instanceof Pair) {
      if (!numbers(car(x)))
        return false;
      x = cdr(x);
    }
    return true;
  }

  static boolean oneof(char c, String s) {
    for (int i = 0; i < s.length(); i++)
      if (c == s.charAt(i))
        return true;
    return false;
  }

  static void p(String s) {
    if (debug)
      Application.debug(s);
  }

  // like pat_match_rl, but search starting right
  public static Object pat_match(Object pat, Object input) {
    Object p = pat_match_rl(mapreverse(pat), mapreverse(input));
    Object r = null;
    while (p instanceof Pair) {
      Pair b = (Pair) car(p);
      if (listq(cdr(b)))
        r = cons(cons(car(b), mapreverse(cdr(b))), r);
      else
        r = cons(b, r);
      p = cdr(p);
    }
    return r;
  }

  public static Object pat_match_rl(Object pat, Object input) {
    if (input == null && pat == null)
      return MATCH;
    if (pat == null)
      return null;
    if (length(input) < length(pat))
      return null;
    Object p = car(pat);
    if (length(pat) == 1) {
      input = list2atom(input);
      if (variableq(p))
        if (matches(p, input))
          return list(cons(p, input));
        else
          return null;
      else if (p.equals(input))
        return MATCH;
      else
        return null;
    }

    if (variableq(p)) {
      Object pr = cdr(pat), r = list(car(input)), q;
      while ((q = pat_match_rl(pr, cdr(input))) == null
          || !matches(p, list2atom(reverse(r)))) {
        input = cdr(input);
        if (car(input) == null)
          return null;
        r = cons(car(input), r);
      }
      r = list2atom(reverse(r));
      if (q == MATCH) // No further Variables, literal match
        return list(cons(p, r));
      else
        return cons(cons(p, r), q);
    } else if (p.equals(car(input)))
      return pat_match_rl(cdr(pat), cdr(input));
    else
      return null;
  }

  // Convert Object from Lisp-String
  public static Object read(String s) throws ParseException {
    return nextObject(new StringBuffer("(" + s + ")"));
  }

  // Conversions from and to lists ("prefix")

  static Object remove(Object x, Object args) {
    if (args instanceof Pair) {
      Object result = null;
      while (args instanceof Pair) {
        if (!car(args).equals(x))
          result = cons(car(args), result);
        args = cdr(args);
      }
      return reverse(result);
    }
    return args;
  }

  public static Object reverse(Object x) {
    Object result = null;
    while (x instanceof Pair) {
      result = cons(car(x), result);
      x = cdr(x);
    }
    return result;
  }

  // Find the first rule in rules that matches input, and apply rule.
  public static Object translator(Object rules, Object input) {
    if (length(rules) == 0)
      return null;
    Object rule = car(rules), match = pat_match(car(rule), input);
    if (match != null)
      return change(cdr(rule), match);
    else
      return translator(cdr(rules), input);
  }

  // Variables are some Strings
  static boolean variableq(Object x) {
    return x instanceof String && ((String) x).length() == 1
        && oneof(((String) x).charAt(0), "xyz");
  }

  static boolean whitespace(char c) {
    return oneof(c, " \t\n\r");
  }

}
